// Time:  O(n + m), m is the number of targets
// Space: O(n)

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {
        vector<pair<int, string>> bucket(s.length());
        /*  // i = 0:
            S.compare(0, 1, "a") == 0  // true
            // Compare "a" with S[0:1]
            bucket[0] = {1, "eee"}
            // Bucket: [(1,"eee"), (0,""), (0,""), (0,"")]

            // i = 1:
            S.compare(2, 2, "cd") == 0  // true
            // Compare "cd" with S[2:4]
            bucket[2] = {2, "ffff"}
            // Bucket: [(1,"eee"), (0,""), (2,"ffff"), (0,"")]
        */
        for (int i = 0; i < indices.size(); ++i)  {
            if (s.compare(indices[i], sources[i].length(), sources[i]) == 0) {
                bucket[indices[i]] = {sources[i].length(), targets[i]};
            }
        }
        string result;
        for (int i = 0; i < s.length();) { 
            if (bucket[i].first) {
                result += bucket[i].second;
                i += bucket[i].first;
            } else {
                result.push_back(s[i++]);
            }
        }
        return result;
    }
};
